package hot100;

public class k6_寻找两个正序数组的中位数 {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        // 确保 nums1 是较短的数组
        if (nums1.length > nums2.length) {
            return findMedianSortedArrays(nums2, nums1);
        }

        int m = nums1.length;
        int n = nums2.length;
        int totalLeft = (m + n + 1) / 2; // 合并后数组的左半部分的元素总数

        // 二分查找的范围
        int left = 0;
        int right = m;

        while (left < right) {
            int i = left + (right - left) / 2; // nums1 的分割点
            int j = totalLeft - i; // nums2 的分割点

            if (nums1[i] < nums2[j - 1]) {
                // i 太小，需要增大
                left = i + 1;
            } else {
                // i 太大，需要减小
                right = i;
            }
        }

        // 二分查找结束，确定分割点
        int i = left;
        int j = totalLeft - i;

        // 处理边界情况
        int nums1MaxLeft = (i == 0) ? Integer.MIN_VALUE : nums1[i - 1];
        int nums1MinRight = (i == m) ? Integer.MAX_VALUE : nums1[i];
        int nums2MaxLeft = (j == 0) ? Integer.MIN_VALUE : nums2[j - 1];
        int nums2MinRight = (j == n) ? Integer.MAX_VALUE : nums2[j];

        // 计算中位数
        if ((m + n) % 2 == 1) {
            // 总数为奇数，中位数是左边部分的最大值
            return Math.max(nums1MaxLeft, nums2MaxLeft);
        } else {
            // 总数为偶数，中位数是左边部分的最大值和右边部分的最小值的平均值
            return (Math.max(nums1MaxLeft, nums2MaxLeft) + Math.min(nums1MinRight, nums2MinRight)) / 2.0;
        }
    }
}
